package com.demoworld;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * Created by francis on 2017/6/14.
 */
public class BinarySearchTest {
    @Test
    public void test1() {
        Assert.assertEquals(-1, binarySearch(new int[]{1, 5, 7, 13, 23, 38, 40, 111}, 6));
    }

    @Test
    public void test2() {
        Assert.assertEquals(-1, binarySearch(new int[]{1, 5, 7, 13, 23, 38, 40, 111}, 500));
    }

    @Test
    public void test3() {
        Assert.assertEquals(0, binarySearch(new int[]{1, 5, 7, 13, 23, 38, 40, 111}, 1));
    }

    @Test
    public void test4() {
        Assert.assertEquals(7, binarySearch(new int[]{1, 5, 7, 13, 23, 38, 40, 111}, 111));
    }

    @Test
    public void test5() {
        Assert.assertEquals(4, binarySearch(new int[]{1, 5, 7, 13, 23, 38, 40, 111}, 23));
    }

    @Test
    public void test6() {
        Assert.assertEquals(3, binarySearch(new int[]{1, 5, 7, 13, 23, 38, 40, 111}, 13));
    }

    @Test
    public void test31() {
        Assert.assertEquals(0, binarySearch(new int[]{1, 5, 7, 13, 23, 38, 40, 111, 211}, 1));
    }

    @Test
    public void test41() {
        Assert.assertEquals(7, binarySearch(new int[]{1, 5, 7, 13, 23, 38, 40, 111, 211}, 111));
    }

    @Test
    public void test51() {
        Assert.assertEquals(4, binarySearch(new int[]{1, 5, 7, 13, 23, 38, 40, 111, 211}, 23));
    }

    @Test
    public void test61() {
        Assert.assertEquals(3, binarySearch(new int[]{1, 5, 7, 13, 23, 38, 40, 111, 211}, 13));
    }


    public int binarySearch(int[] arr, int x) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (x < arr[0]) {
            return -1;
        }
        if (x > arr[arr.length - 1]) {
            return -1;
        }
        int returnIndex = -1;
        int startIndex = 0;
        int endIndex = arr.length - 1;
        int middleIndex = (startIndex + endIndex) / 2;
        while (true) {
            if (x == arr[startIndex]) {
                returnIndex = startIndex;
                break;
            }
            if (x == arr[endIndex]) {
                returnIndex = endIndex;
                break;
            }
            if (x == arr[middleIndex]) {
                returnIndex = middleIndex;
                break;
            }
            if (middleIndex == startIndex || middleIndex == endIndex) {
                break;
            }
            if (x > arr[middleIndex]) {
                startIndex = middleIndex;
            }
            if (x < arr[middleIndex]) {
                endIndex = middleIndex;
            }
            middleIndex = (startIndex + endIndex) / 2;
        }
        return returnIndex;
    }
}
